Search for: All records

The recent proliferation of NISQ devices has made it imperative to understand their power. In this work, we define and study the complexity class , which encapsulates problems that can be efficiently solved by a classical computer with access to noisy quantum circuits. We establish super-polynomial separations in the complexity among classical computation, , and fault-tolerant quantum computation to solve some problems based on modifications of Simon’s problems. We then consider the power of for three well-studied problems. For unstructured search, we prove that cannot achieve a Grover-like quadratic speedup over classical computers. For the Bernstein-Vazirani problem, we show that only needs a number of queries logarithmic in what is required for classical computers. Finally, for a quantum state learning problem, we prove that is exponentially weaker than classical computers with access to noiseless constant-depth quantum circuits. 

We present a discrete basis of solutions of the massless Klein-Gordon equation in 3 + 1 Minkowski space which transform as 𝔰𝔩(2, ℂ) Lorentz/conformal primaries and descendants, and whose elements all have integer conformal dimension. We show that the basis is complete in the sense that the Wightman function can be expressed as a quadratic sum over the basis elements. 

Producing quantum states at random has become increasingly important in modern quantum science, with applications being both theoretical and practical. In particular, ensembles of such randomly distributed, but pure, quantum states underlie our understanding of complexity in quantum circuits1 and black holes2, and have been used for benchmarking quantum devices3,4 in tests of quantum advantage5,6. However, creating random ensembles has necessitated a high degree of spatio-temporal control7,8,9,10,11,12 placing such studies out of reach for a wide class of quantum systems. Here we solve this problem by predicting and experimentally observing the emergence of random state ensembles naturally under time-independent Hamiltonian dynamics, which we use to implement an efficient, widely applicable benchmarking protocol. The observed random ensembles emerge from projective measurements and are intimately linked to universal correlations built up between subsystems of a larger quantum system, offering new insights into quantum thermalization13. Predicated on this discovery, we develop a fidelity estimation scheme, which we demonstrate for a Rydberg quantum simulator with up to 25 atoms using fewer than 104 experimental samples. This method has broad applicability, as we demonstrate for Hamiltonian parameter estimation, target-state generation benchmarking, and comparison of analogue and digital quantum devices. Our work has implications for understanding randomness in quantum dynamics14 and enables applications of this concept in a much wider context 4,5,9,10,15,16,17,18,19,20. 

Quantum technology promises to revolutionize how we learn about the physical world. An experiment that processes quantum data with a quantum computer could have substantial advantages over conventional experiments in which quantum states are measured and outcomes are processed with a classical computer. We proved that quantum machines could learn from exponentially fewer experiments than the number required by conventional experiments. This exponential advantage is shown for predicting properties of physical systems, performing quantum principal component analysis, and learning about physical dynamics. Furthermore, the quantum resources needed for achieving an exponential advantage are quite modest in some cases. Conducting experiments with 40 superconducting qubits and 1300 quantum gates, we demonstrated that a substantial quantum advantage is possible with today’s quantum processors.